﻿/*THÔNG TIN*********************************************************************
 *Tập tin		: Graph/DAG.h
 *Mô tả			: Thư viện các với các phương thức với đồ thị vô hướng không có chu trình
 *Ngày tạo		: 25/09/2012
 *Cập nhật cuối	: 07/11/2012
 *Trình dịch	: Microsoft Visual C++ 11.0
 *Tác giả		: Vũ Văn Hiệp
 *Thư điện tử	: muteszhacker@gmail.com
*******************************************************************************/

/*Lớp các phương thức với đồ thị vô hướng không có chu trình*/
class DAG : public GRAPH	{
public:
	// Phương thức khởi tạo
	DAG();

	// Khởi tạo cho thuật toán Topo
	void Initiate_Topo();
	//Tính bậc của các đỉnh
	void Calc_deg(vector <uint16_t> &deg);
	// Thuật toán Topo đánh số lại các đỉnh
	void Topological_order();
	// In kết quả đánh số ra file .out
	void Print_result_to_out(string input_file);

	// In đồ thị ban đầu và đồ thị mới được đánh số lại
	void Print_result_to_dot(string input_file);
};/*Kết thúc khai báo lớp DAG*/

/*Phương thức khởi tạo*/
DAG :: DAG()	{
	result.clear();
}/*Kết thúc phương thức DAG*/

/*Khởi tạo cho thuật toán Topo*/
void DAG :: Initiate_Topo()	{
	result.resize(Get_vertices());
	fill(result.begin(), result.end(), UINT16_MAX);

	cout << "Thuc hien thuat toan Topo..........";
	start_time = clock();
}/*Kết thúc phương thức Initiate_Topo*/

/*Tính bậc của các đỉnh*/
void DAG :: Calc_deg(vector <uint16_t> &deg)	{
	for (uint16_t i=0; i!=Get_vertices(); ++i)
		for (uint16_t j=0; j!=Get_vertices(); ++j)
			if (Get_length(i, j) != UINT16_MAX)
				++deg[j];
}/*Kết thúc phương thức Calc_deg*/

/*Thuật toán Topo đánh số lại các đỉnh*/
void DAG :: Topological_order()	{
	vector <uint16_t> deg(Get_vertices());
	Calc_deg(deg);

	// Khởi tạo queue, cho các đỉnh có bậc = 0 vào hàng đợi queue
	vector <uint16_t> queue(Get_vertices(), UINT16_MAX);
	uint16_t i, left = 0, right = 0, num = 0;

	for (i=0; i!=Get_vertices(); ++i)
		if (deg[i] == 0)
			queue[right++] = i;

	// Đánh số lại đỉnh
	while (left < right)	{
		i = queue[ left++ ];
		result[i] = (num++);

		for (uint16_t j=0; j!=Get_vertices(); ++j)
			if (Get_length(i, j) != UINT16_MAX)	{
				--deg[j];

				if (deg[j] == 0)
					queue[ right++ ] = j;
			}
	}

	Print_runtime();
}/*Kết thúc phương thức Topological_order*/

/*In kết quả đánh số ra file .out*/
void DAG :: Print_result_to_out(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "_Topo", ".out");

	// Kiểm tra nếu đồ thị có chu trình
	for (uint16_t i=0; i!=Get_vertices(); ++i)
		if (result[i] == UINT16_MAX)	{
			f << "Do thi vua nhap co chu trinh.\n";
			cout << "Xong.\n";
			f.close();
			return;
		}

	// In thứ tự đỉnh mới ra file
	f << "Thu tu cac dinh moi la: \n";

	for (uint16_t i=0; i!=result.size(); ++i)
		f << result[i]+1 << " ";
	
	f << "\n";
	f.close();
	cout << "Xong.\n";
}/*Kết thúc phương thức Print_result_to_out*/

/*In đồ thị ban đầu và đồ thị mới được đánh số lại và dịch từ .dot sang hình ảnh .bmp*/
void DAG :: Print_result_to_dot(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "_Topo", ".dot");

	// Bắt đầu lưu đồ thị ra file .dot
	f << "digraph " << input_header << "_Topo" << " {\n";

	uint16_t k;

	for (k=0; k!=Get_vertices(); ++k)
		if (result[k] == UINT16_MAX)	{
			f << "label = \"\\n\\nDo thi nhap tu file " << input_file << " co chu trinh.\"\n}";
			break;
		}

	if (k == Get_vertices())	{
		for (uint16_t i=0; i<Get_vertices(); ++i)
			for (uint16_t j=0; j<Get_vertices(); ++j)
				if (Get_length(i, j) != UINT16_MAX)
					f << i+1 << "." << result[i]+1 << " -> " << j+1 << "." << result[j]+1 
					  << " [label = \"" << Get_length(i, j) << "\"]\n";

		f << "label = \"\\n\\nDo thi duoc danh so lai nho thuat toan Topo\\nvoi du lieu tu file " << input_file << ".\"\n}";
	}

	f.close();
	cout << "Xong.\n";
}/*Kết thúc phương thức Print_result_to_dot*/
